package top.lcm889.oj.leetcodeTop200;

import top.lcm889.oj.databean.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Coder-lcm
 * @date 2021/4/7
 *     BFS: 广度优先遍历算法
 *
 */
public class LC111_树的最小深度 {

    /**
     * 求二叉树的最小深度
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 核心数据结构，存储一层的节点，方便进行分散
        queue.offer(root); // 把根节点放进去
        int depth = 1;//最小深度
        // 当队列不为空时
        while (!queue.isEmpty()) {
            int size = queue.size(); // 队列的长度，即当前层下的所有节点
            // 遍历同层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return depth; // 已经找到了树的最小深度
                }else if (node.left != null) {
                    // 如果左子树不为空，把左子树节点加入队列（下一层再遍历）
                    queue.offer(node.left);
                }else if (node.right != null) {
                    // 如果右子树不为空，把右子树节点加入队列（下一层再遍历）
                    queue.offer(node.right);
                }
            }
            // 深度 + 1
            depth++;
        }
        return depth;
    }

    /**
     * 二叉树的层序遍历（也属于BFS的一种）
     * @param root
     * @return
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root == null) return new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//        ArrayList<Integer> rootVal = new ArrayList<>();
//        rootVal.add(root.val);
//        res.add(rootVal);
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 核心数据结构，存储一层的节点，方便进行分散
        queue.offer(root); // 把根节点放进去
        // 当队列不为空时
        while (!queue.isEmpty()) {
            int size = queue.size(); // 队列的长度，即当前层下的所有节点
            ArrayList<Integer> cur = new ArrayList<>();
            // 遍历同层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                cur.add(node.val);
                if (node.left != null) {
                    // 如果左子树不为空，把左子树节点加入队列（下一层再遍历）
                    queue.offer(node.left);
                    System.out.println(node.right.val);
                }
                if (node.right != null) {
                    // 如果右子树不为空，把右子树节点加入队列（下一层再遍历）
                    queue.offer(node.right);
                }
            }
            res.add(cur);
        }
        return res;
    }

    public static void main(String[] args) {
        LC111_树的最小深度 test = new LC111_树的最小深度();
        TreeNode treeNode = new TreeNode(3,
                new TreeNode(9), new TreeNode(20,
                            new TreeNode(15), new TreeNode(7)));
        // 1. BFS求最小深度
//        int minDepth = test.minDepth(treeNode);
//        System.out.println(minDepth);

        // 2.BFS求层序遍历
        ArrayList<ArrayList<Integer>> res = test.levelOrder(treeNode);
        res.forEach(each -> {
            each.forEach(e -> {
                System.out.print(e + ",");
            });
        });


    }

}

